package 题目集.图.最短路;// package acm.pta10;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class 直捣黄龙 {
    public static void main(String[] args) {
        Reader sc = new Reader();
        Graph graph = new Graph();
        int n = sc.nextInt();
        int m = sc.nextInt();
        String start = sc.next();
        String end = sc.next();
        graph.addNode(new Node(start, 0));
        while (--n > 0) {
            Node node = new Node(sc.next(), sc.nextInt());
            graph.addNode(node);
        }
        while (m-- > 0) {
            graph.addEdge(sc.next(), sc.next(), sc.nextInt());
        }
        Info res = dijkstra(graph, graph.map.get(start), graph.map.get(end));
        StringBuilder sb = new StringBuilder();
        getStr(res, sb);
        sb.delete(sb.length() - 2, sb.length());
        System.out.println(sb);
        System.out.println(plan + " " + res.time + " " + res.total);
    }

    public static void getStr(Info info, StringBuilder sb) {
        if (info == null) return;
        getStr(info.pre, sb);
        sb.append(info.name).append("->");
    }

    static int plan;

    public static Info dijkstra(Graph graph, Node start, Node end) {
        PriorityQueue<Info> queue = new PriorityQueue<>();
        Set<String> visited = new HashSet<>();
        Map<String, Info> map = new HashMap<>();
        Info info = new Info(start.name, 0, 0, 0, null);
        queue.add(info);
        start.plan = 1;
        while (!queue.isEmpty()) {
            info = queue.poll();
            if (visited.contains(info.name)) {
                continue;
            }
            if (info.name.equals(end.name)) break;
            visited.add(info.name);
            Node curr = graph.get(info.name);
            for (Edge edge : curr.next) {
                int newTime = info.time + edge.time;
                //已经访问过或者比原先距离远
                if (visited.contains(edge.to.name)
                        || newTime > edge.to.time
                ) continue;
                //比原来近
                if (newTime < edge.to.time) {
                    edge.to.plan = curr.plan;
                    edge.to.time = newTime;
                } else {
                    edge.to.plan += curr.plan;    //新路线
                }
                Info to = new Info(edge.to.name, newTime, info.pass + 1, info.total + edge.to.count, info);
                if (to.compareTo(map.get(edge.to.name)) < 0) {  //比原来优
                    queue.add(to);
                    map.put(to.name, to);
                }
            }
        }

        plan = graph.get(info.name).plan;
        return info;
    }

    static class Info implements Comparable<Info> {
        String name;
        int time;
        int pass;
        int total;
        Info pre;

        public Info(String name, int time, int pass, int total, Info pre) {
            this.name = name;
            this.time = time;
            this.pass = pass;
            this.total = total;
            this.pre = pre;
        }

        @Override
        public int compareTo(Info other) {
            if (other == null) return -1;
            if (time == other.time) {
                if (pass == other.pass) {
                    return other.total - total;
                }
                return other.pass - pass;
            }
            return time - other.time;
        }
    }

    static class Graph {
        Map<String, Node> map = new HashMap<>();

        public void addNode(Node o) {
            map.put(o.name, o);
        }

        public Node get(String key) {
            return map.get(key);
        }

        public void addEdge(String from, String to, int time) {
            Node fromNode = map.get(from);
            Node toNode = map.get(to);
            Edge from_to = new Edge(fromNode, toNode, time);
            Edge to_from = new Edge(toNode, fromNode, time);
            fromNode.next.add(from_to);
            toNode.next.add(to_from);
        }
    }

    static class Node {
        String name;
        int time = Integer.MAX_VALUE;
        int count;
        int plan;
        List<Edge> next = new LinkedList<>();

        public Node(String name, int count) {
            this.name = name;
            this.count = count;
        }
    }

    static class Edge {
        Node from;
        Node to;
        int time;

        public Edge(Node from, Node to, int time) {
            this.from = from;
            this.to = to;
            this.time = time;
        }
    }

    static
    class Reader {
        private BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        private StringTokenizer tokenizer = new StringTokenizer("");

        private String innerNextLine() {
            try {
                return reader.readLine();
            } catch (IOException ex) {
                return null;
            }
        }

        public boolean hasNext() {
            while (!tokenizer.hasMoreTokens()) {    //内存中没有
                String nextLine = innerNextLine();
                if (nextLine == null) {     //且没有下一行
                    return false;
                }
                tokenizer = new StringTokenizer(nextLine);  //读入一行
            }
            return true;
        }

        public String nextLine() {
            tokenizer = new StringTokenizer("");    //清空内存中的字符
            return innerNextLine();
        }

        public String next() {
            hasNext();
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }
//    public BigInteger nextBigInt() {
//        return new BigInteger(next());
//    }
    }

}

